package com.dmall.chapter07.section05;


import java.util.*;
import java.util.stream.Collectors;

/**
 * 农夫过河问题，把未过河之前的状态定义为0000，都过河的状态定义为1111
 * 第一位代表农夫
 * 第二位代表狼
 * 第三位代表羊
 * 第四位代表菜
 * 但是这个问题有deadends，deadends=[0011, 0110, 1100, 1001, 0111, 1000]
 *      deadends的第一种状态为农夫和狼在河这边，羊和菜在河对岸
 *      deadends的第二种状态为农夫和菜在河这边，狼和羊在河对岸
 *      deadends的第三种状态为羊和菜在河这边，农夫和狼在河对岸
 *      deadends的第四种状态为狼和羊在河这边，农夫和菜在河对岸
 *      deadends的第五种状态为农夫在河这边，狼和羊和菜在河对岸
 *      deadends的第六种状态为狼和羊和菜在河这边，农夫在河对岸
 * 由于船最多能装下农夫、狼、羊、菜之中的其中两样，并且船要开的话必须要有农夫
 * 那么从一个状态变化到另一个状态的可能：
 * 比如最初状态为：0000 --> [1000, 1100, 1010, 1001]
 *      1000表示农夫一个人划船过河（不允许：狼要吃羊，羊要吃菜）
 *      1100表示农夫带着狼过河（不允许：羊要吃菜）
 *      1010表示农夫带着羊过河
 *      1001表示农夫带着菜过河（不允许：狼要吃羊）
 */
public class FarmerAcrossRiver {

    private final String[] deadends = {"0011", "0110", "1100", "1001", "0111", "1000"};
    private Set<String> deadSet = Arrays.stream(deadends).collect(Collectors.toSet());
    private Map<String, String> pre = new LinkedHashMap<>();
    private Map<String, Integer> visited = new HashMap<>();
    private String start = "0000";
    private String end = "1111";

    public FarmerAcrossRiver() {
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        visited.put(start, 0);
        pre.put(start, start);

        while (!queue.isEmpty()) {
            String cur = queue.remove();
            List<String> nexts = getNexts(cur);
            for (String next : nexts) {
                if (!deadSet.contains(next) && !visited.containsKey(next)) {
                    queue.add(next);
                    visited.put(next, visited.get(cur) + 1);
                    pre.put(next, cur);
                    if (end.equals(next)) {
                        return;
                    }
                }
            }
        }
    }

    private List<String> getNexts(String s) {
        List<String> result = new ArrayList<>();
        char[] chars = s.toCharArray();
        char char_1 = chars[1];
        char char_2 = chars[2];
        char char_3 = chars[3];

        chars[0] = Character.forDigit((chars[0] - '0' + 1) % 2, 10);
        result.add(new String(chars));

        chars[1] = Character.forDigit((chars[1] - '0' + 1) % 2, 10);
        result.add(new String(chars));
        chars[1] = char_1;

        chars[2] = Character.forDigit((chars[2] - '0' + 1) % 2, 10);
        result.add(new String(chars));
        chars[2] = char_2;

        chars[3] = Character.forDigit((chars[3] - '0' + 1) % 2, 10);
        result.add(new String(chars));
        chars[3] = char_3;

        return result;
    }

    private int stepCount() {
        if (visited.containsKey(end)) {
            return visited.get(end);
        } else {
            return -1;
        }
    }

    private List<String> step() {
        List<String> res = new ArrayList<>();
        if (!visited.containsKey(end)) {
            return res;
        }
        String cur = end;
        while (!cur.equals(start)) {
            res.add(cur);
            cur = pre.get(cur);
        }
        res.add(start);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        FarmerAcrossRiver farmerAcrossRiver = new FarmerAcrossRiver();
        System.out.println(farmerAcrossRiver.stepCount());
        System.out.println(farmerAcrossRiver.step());
    }
}
